<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include &lt;cstdio&gt;
#include &lt;cassert&gt;
#include &lt;vector&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)
#define fornd(i, n) for (int i = (int)(n) - 1; i &gt;= 0; i--)
#define forab(i, a, b) for (int i = (int)(a); i &lt;= (int)(b); i++)
#define sz(a) (int)(a).size()
#define pb push_back

const int maxn = (int)5e4 + 10;
const int maxk = 18;

int n, m, T, in[maxn], out[maxn];
int p[maxk][maxn];
vector &lt;int&gt; c[maxn];

void go( int v )
{
  in[v] = T++;
  forn(i, sz(c[v]))
    go(c[v][i]);
  out[v] = T++;
}

inline int isA( int p, int a )
{
  return in[p] &lt;= in[a] && out[a] &lt;= out[p];
}

int main()
{
  #define NAME "lca"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  scanf("%d", &n);
  forab(i, 2, n)
    scanf("%d", &p[0][i]), c[p[0][i]].pb(i);

  p[0][1] = 1;
  forab(k, 1, maxk - 1)
    forab(i, 1, n)
      p[k][i] = p[k - 1][p[k - 1][i]];
  go(1);

  scanf("%d", &m);
  while (m--)
  {
    int a, b;
    scanf("%d%d", &a, &b);

    fornd(k, maxk)
      if (!isA(p[k][a], b))
        a = p[k][a];
    if (!isA(a, b))
      a = p[0][a];
    printf("%d\n", a);
  }
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
